package wtx.leetcode;

// solution from: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/351201/DP-solution-faster-than-100-with-explanation
class Solution {
  public int maxProfit(int k, int[] prices) {
      return maxProfitDP(prices, k);
  }
  private int maxProfitDP(int[] prices, int transactions){
      /* f[k,i] represents max profit with K transactions and trading ending at day i
      There are two possiblities
         either we ignore day i, that means max profit is nothing but f[k, i-1]
         or we seel on day i, which means which must have purchased at some prior day
         j such that price[i] - price[j] + f[k-1, j] is maximum.
         
         f[0,i] = 0 as wth zero transaction you cannnot earn anything
         f[k,0] = 0 as nothing can be earned by zero  data points
      */
      
      if(prices.length == 0) return 0;
      
      /*This case handles the possibility that you may be allowed to have more than 
       n/2 transactions, in this case, we can buy and sell on each possible day and
       maximize the problem.
       */
      if (transactions >=  prices.length/2) {
      int maxPro = 0;
      for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i-1])
          maxPro += prices[i] - prices[i-1];
      }
      return maxPro;
    }
      
      int[][] f = new int[2][prices.length];
      f[0][0] = 0;
      // 這種思路值得借鑒
      /*To avoid the memory limit exceeded, only two rows are used
      as we need only k-1 and k transaction rows, everything else 
      can be done away with */
      
      for(int k=1; k<=transactions; k++){
          int tempMax =  f[0][0] - prices[0];
          for(int i=1; i<prices.length; i++){
              f[1][i] = Math.max(prices[i] + tempMax, f[1][i-1]);
              tempMax = Math.max(tempMax, f[0][i] - prices[i]);
              f[0][i] = f[1][i];
          }
      }
      
      return f[0][prices.length-1];
  }
}